#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int get_d(int a, int b) {
        int x1 = a / 3, y1 = a % 3;
        int x2 = b / 3, y2 = b % 3;
        return abs(x1 - x2) + abs(y1 - y2);
    }

    void dfs(int u, int n,vector<bool>& st,vector<int>& p,vector<int>& in,vector<int>& ou,int& ans) {
        if (u == n) {
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                //  cout<<p[i]<<" ";
                cnt += get_d(ou[i], in[p[i]]);
            }
            //cout<<endl;
        // cout<<"cnt=="<<cnt<<endl;
            ans = min(ans, cnt);
        }


        for (int i = 0; i < n; i++) {
            if (!st[i]) {
                p[u] = i;
                st[i] = true;
                dfs(u + 1, n, st, p, in, ou, ans);
                st[i] = false;
            }
        }
    }

    int minimumMoves(vector<vector<int>>& grid) {
        vector<int> ou;
        vector<int> in;
        vector<bool> st(10, false);
        vector<int> p(10, 0);
        int ans = 1e9;

        int  n = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid[i][j] == 0) {
                    int k = i * 3 + j;
                    in.push_back(k);
                    n++;
                }
                else if (grid[i][j] > 1) {
                    int k = i * 3 + j;
                    int num = grid[i][j];
                    while (num > 1) {
                        ou.push_back(k);
                        num--;
                    }
                }
            }
        }
        // for(auto it:in){
        //     cout<<it<<" ";
        // }
        // cout<<endl;
        // for(auto it:ou){
        //     cout<<it<<" ";
        // }
        // cout<<endl;

        dfs(0, n, st, p, in, ou, ans);
        return ans;
    }
};  